package leetcode.year2021.month10;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class _01_02Combine77 {
  public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new ArrayList<>();

    if (n < k || k <= 0) {
      return ans;
    }

    Deque<Integer> stack = new ArrayDeque<>();

    dfs(n,1,k,stack,ans);

    return ans;
  }

  public static void dfs(int n, int begin, int k, Deque<Integer> stack, List<List<Integer>> ans) {
    if (stack.size() == k){
      ans.add(new ArrayList<>(stack));
      return;
    }

    for (int i = begin; i <= n - (k - stack.size()) + 1; i++) {
      stack.add(i);
      dfs(n,i+1,k,stack,ans);
      stack.removeLast();
    }
  }

  /**
   * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
   *
   * 你可以按 任何顺序 返回答案。
   *
   *  
   *
   * 示例 1：
   *
   * 输入：n = 4, k = 2
   * 输出：
   * [
   *   [2,4],
   *   [3,4],
   *   [2,3],
   *   [1,2],
   *   [1,3],
   *   [1,4],
   * ]
   * 示例 2：
   *
   * 输入：n = 1, k = 1
   * 输出：[[1]]
   */
}
